package com.chj.zhongji.class07;

//https://www.nowcoder.com/questionTerminal/30fb9b3cab9742ecae9acda1c75bf927
public class Code02_LIS {

	public static int[] lis1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return null;
		}
		int[] dp = getdp1(arr);
		return generateLIS(arr, dp);
	}

	public static int[] getdp1(int[] arr) {
		int[] dp = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (arr[i] > arr[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}
		return dp;
	}

	public static int[] generateLIS(int[] arr, int[] dp) {
		int len = 0;
		int index = 0;
		for (int i = 0; i < dp.length; i++) {
			if (dp[i] > len) {
				len = dp[i];
				index = i;
			}
		}
		int[] lis = new int[len];
		lis[--len] = arr[index];
		for (int i = index; i >= 0; i--) {
			if (arr[i] < arr[index] && dp[i] == dp[index] - 1) {
				lis[--len] = arr[i];
				index = i;
			}
		}
		return lis;
	}

	public static int[] lis2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return null;
		}
		int[] dp = getdp2(arr);
		return generateLIS(arr, dp);
	}

	public static int[] getdp2(int[] arr) {
		int[] dp = new int[arr.length];
		int[] ends = new int[arr.length];
		ends[0] = arr[0];
		dp[0] = 1;
		int right = 0;
		int l = 0;
		int r = 0;
//		int m = 0;
		for (int i = 1; i < arr.length; i++) {
			l = 0;
			r = right;
//			while (l <= r) {
//				m = (l + r) / 2;
//				if (arr[i] > ends[m]) {
//					l = m + 1;
//				} else {
//					r = m - 1;
//				}
//			}
			l = left_bound(ends, arr[i], l, r);
			right = Math.max(right, l);
			ends[l] = arr[i];
			dp[i] = l + 1;
		}
		return dp;
	}

	public static int left_bound(int[] nums, int target, int l, int r) {
		int left = l, right = r;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] < target) {
				left = mid + 1;
			} else if (nums[mid] > target) {
				right = mid - 1;
			} else if (nums[mid] == target) {
				// 别返回，锁定左侧边界
				right = mid - 1;
			}
		}
		// 最后要检查 left 越界的情况
//		if (left >= nums.length || nums[left] != target)
//			return -1;
		return left;
	}

	// for test
	public static void printArray(int[] arr) {
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		{
			int[] arr = { 2, 1, 5, 3, 6, 4, 8, 9, 7 };
			printArray(arr);
			printArray(lis1(arr));
			printArray(lis2(arr));
		}
		System.out.println();
		{
			int[] arr = { 1, 2, 8, 6, 4 };
			printArray(arr);
			printArray(lis1(arr));
			printArray(lis2(arr));
		}

	}
}